package code;

import java.util.List;

public class Code52 {
	
	/*
	 * N-Queens
	 * dfs生成
	 */
	private int cnt;
	
	public void generateNQueens(int n,int x,int[] Y){
		/*
		 * 已经添加完了吗？
		 */
		int i,j;
		if(x==n){
			cnt++;
		}
		for(i=0;i<n;i++){
			if(isOk(i,Y,x)){
				Y[x]=i;
				generateNQueens(n,x+1,Y);
			}
		}
	}
	/*
	 * 判断第x行的第y列是否能放Queen,Y[0..x]保存的是已经放的Queen
	 */
	public boolean isOk(int y,int[] Y,int x){
		
		for(int i=0;i<x;i++){
			if(Y[i]==y)
				return false;
			/*
			 * 在对角线上？
			 */
			if(Math.abs(x-i)==Math.abs(y-Y[i]))
				return false;
		}
		return true;
	}
    public int totalNQueens(int n) {
        cnt=0;
    	int[] Y=new int[n];
    	generateNQueens(n, 0, Y);
    	return cnt;
    }
    public static void main(String[] args){
    	new Code52().totalNQueens(8);
    }
}
